
//dynamic programming

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

FILE *fp;
int C;     // capacity of the knapsack (total weight that can be stored)
int N;    // number of items available
int *w;  // vector of item weights
int *v;  // vector of item profits or values
int *kindex;  // a list of indexes (we can sort these instead of moving the items)
int QUIET=0; // this can be set to 1 to suppress output

// function prototypes
extern void read_knapsack_instance(char *filename);
int DP(int *v,int *wv, int n, int W, int *x);
extern int print_sol2(int *s,  int *tv, int *tw);

int main(int argc, char *argv[1])
{
  int *x;    // binary vector indicating items to pack
  int tv, tw;  // total value and total weight of items packed
  
  read_knapsack_instance(argv[1]);

  if((x = (int *)malloc((N+1)*sizeof(int)))==NULL)
    {      
      fprintf(stderr,"Problem allocating table for DP\n");
      exit(1);
    }

  DP(v,w,N,C,x);
  print_sol2(x,&tw,&tv);
  return(0);
}
  
int DP(int *v,int *wv, int n, int W, int *x)
{
  // the dynamic programming function for the knapsack problem
  // the code was adapted from p17 of http://www.es.ele.tue.nl/education/5MC10/solutions/knapsack.pdf

  // v array holds the values / profits / benefits of the items
  // wv array holds the sizes / weights of the items
  // n is the total number of items
  // W is the constraint (the weight capacity of the knapsack)
  // x is the binary solution vector, a 1 in position n means pack item number n+1. A zero means do not pack it.

  int **V, **keep;  // 2d arrays for use in the dynamic programming solution
  // keep[][] and V[][] are both of size (n+1)*(W+1)

  int i, w, K;

  // Dynamically allocate memory for variables V and keep
  /* ADD CODE HERE */
  V = (int **) malloc (sizeof (int *) * (n+1));
  keep =  (int **) malloc (sizeof (int *) * (n+1));
  
  for (i = 0; i< n+1; i++)
  {
    V[i] = (int *)malloc((C+1)*sizeof(int));
    keep[i] = (int *)malloc((C+1)*sizeof(int));
  }
 //  set the values of the zeroth row of the partial solutions table to zero
  /* ADD CODE HERE */
  for (w=0; w<W;w++)
  {
    V[0][w] = 0;
  }

 // main dynamic programming loops , adding one item at a time and looping through weights
  /* ADD CODE HERE */
  for (i=1;i<=n;i++)
  {
    for (w=0;w<W+1;w++)
    {
      if ((wv[i] < w)&&(v[i] + V[i-1][w-wv[i]] > V[i-1][w]))
      {
        V[i][w] = v[i] + V[i-1][w-wv[i]];
        keep[i][w]=1;
      }
      else
      {
        V[i][w] = V[i-1][w];
        keep[i][w] = 0;
      }
    }
    
  } 
    K = W;
  
  // now discover which items were in the optimal solution
  /* ADD CODE HERE */
    for (i=n;i>=1;i--)
    {
      
      x[i]=0;
      if(keep[i][K] == 1)
      {
        x[i]=1;
        printf("%d\n", i);
        K = K - wv[i];
      }
    }
    
  return V[n][W];
}


